package 数据结构专栏.简单级别;

/**
 * @DESC
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * @Author tzq
 * @Date 2020-04-03 09:28
 **/
public class _111_二叉树的最小深度 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(3);
        TreeNode t2 = new TreeNode(9);
        TreeNode t3 = new TreeNode(20);
        TreeNode t4 = new TreeNode(15);
        TreeNode t5 = new TreeNode(7);
        t1.left = t2;
        t1.right = t3;
        t3.left= t4;
        t3.right = t5;
        System.out.println(new _111_二叉树的最小深度().minDepth(t1));

        TreeNode o1 = new TreeNode(3);
        TreeNode o2 = new TreeNode(9);
        o1.left = o2;
        System.out.println(new _111_二叉树的最小深度().minDepth(o1));


    }


    /**
     * 我的解法
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;

        int min = Integer.MAX_VALUE;
        if (root.left != null) {
            min = Math.min(minDepth(root.left),min);
        }
        if (root.right != null) {
            min = Math.min(minDepth(root.right),min);
        }
        return min + 1;
    }

    /**
     * 错误解法2： 当有2个节点的时候不行
     * @param root
     * @return
     */
    public int minDepth2(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
    }
}
